package 我的Java学习_算法基础.day_03;


import java.util.Random;

import static 我的Java学习_算法基础.day_01.唯一成对的数.printArray;

public class _033_快排之单向扫描分区法 {
    public static void main(String[] args) {
        int[] array = new int[20];
        Random random = new Random();
        for (int i = 0 ;i<array.length;i++){
            array[i]= random.nextInt(20);
        }
        printArray(array);
        quickSort(array,0,array.length-1);
        printArray(array);
    }
    public static void quickSort(int[] array,int p,int r){
        if(p<r){
            int q = partition(array,p,r);
            quickSort(array,p,q-1);
            quickSort(array,q+1,r);
        }
    }
    public static int partition(int[] array,int p,int r){
        int pivot = array[p];   //第一个元素作为基元
        int sp = p+1;       //扫描指针
        int bigger = r;     //右侧指针
        while(sp<=bigger){
            if(array[sp]<=pivot){//扫描元素小于等于基元，扫描指针右移
                sp++;
            }else{  //大于，扫描元素与右侧指针指向元素交换，右侧指针左移
                int a = array[sp];
                array[sp]=array[bigger];
                array[bigger]=a;
                bigger--;
            }

        }
        int a = array[p];           //最后，基元与右侧指针指向元素交换
        array[p]=array[bigger];
        array[bigger]=a;
        return bigger;
    }
}
